[Overview] [Previous] [Next]

Primitive Regular Expressions

A regular expression can be used to define a language. A regular expression represents a "pattern;" strings that match the pattern are in the language, strings that do not match the pattern are not in the language.

As usual, the strings are over some alphabet sigma .

Important! The following are primitive regular expressions:

x, for each x ,
, the empty string, and
, indicating no strings at all.

Thus, if | sigma

| = n, then there are n+2 primitive regular expressions defined over sigma

Here are the languages defined by the primitive regular expressions:

For each x , the primitive regular expression x denotes the language {x}. That is, the only string in the language is the string "x".
The primitive regular expression denotes the language {}. The only string in this language is the empty string.
The primitive regular expression denotes the language {}. There are no strings in this language.